An Introduction to Kernel Methods

Kernel Methods

이번 포스트에서는 저번에 살펴본 커널함수를 이용한 방법론들을 살펴보고자 한다. 커널에 의해 정의된 유사성 행렬^{similarity matrix} 을 입력받아 처리하는 알고리즘을 Kernel Methods 라고 한다. 앞서 살펴본 것 처럼 커널은 유사성의 측도로도 정의되고, 데이터공간의 원소들을 커널에 입력하면 실행렬을 얻을 수 있는데, 이를 유사성 행렬이라 한다. 우선, 대부분의 커널 방법론들의 근간에는 두 가지 개념이 있는데, Kernel Trick과 Representer Theorem이다.

Kernel Trick

커널 트릭의 내용은 이전 게시글에서 살펴본 내적으로서의 커널 함수의 개념과 유사하다.

벡터형 데이터를 처리하는 알고리즘 중 오직 점곱 형태로만 표현될 수 있는 것들은 특성공간^{feature space} 에서 커널을 이용해 암묵적으로^Implicitly 수행될 수 있다.

커널이 특성공간에서 내적으로 정의된다는 점을 고려할 때 위 명제는 당연한 것처럼 보인다. 그러나, 당연한 명제임에도 실제 알고리즘에 적용될 때에는 기대 이상으로 효과적일 수 있다. 예를 들어, PCA나 LDA와 같은 선형 알고리즘의 경우, 일반적인 내적 대신에 가우시안 방사커널을 이용하게 되면 이를 비선형문제로 치환할 수 있다. 다음과 같은 대상간 거리 측정에서의 예시도 살펴보자.

예시 - 객체 간 거리측정 문제

Input space $\mathbf{X}$에 커널 $k$가 정의되어있고, 이때 $\mathbf{X}$의 점들간의 거리를 측정하는 문제를 고려하자. 이전에 살펴본 것처럼, 커널은 점곱으로 표현될 수 있다. 따라서 점곱이 정의된 공간 $\mathcal{F}$ 으로의 사상 $\phi:\mathbf{X}\to \mathcal{F}$ 이 정의된다면 커널을 $k(\mathbf{x,x’})=\langle\mathbf{\phi(x),\phi(x’)}\rangle$ 로 표현할 수 있다.

유한집합 $\mathcal{S}=(\mathbf{x_1,\ldots,x_n})$ 이 주어진 데이터 객체들의 모임이라고 해보자. 즉, $\mathcal{S}\subset\mathbf{X}$ 이다. 이때 주어진 임의의 $\mathbf{x\in X}$ 가 집합 $\mathcal{S}$ 에 어느 정도로 가깝고 먼지, 거리(dist)를 측정하는 상황을 생각하자. 예컨대 K-nearest neighborhood 문제에서 특정 객체의 클래스를 분류할 때 주어진 K개의 이웃들과의 거리를 측정하는 상황을 생각하면 될 것이다. 만약 특성공간으로의 사상 $\phi:\mathbf{X}\to \mathcal{F}$ 가 주어진다면, 우리는 간단하게 해당 거리(dist)를 다음과 같이 정의할 수 있다.

\[dist(\mathbf{x},\mathcal{S}) = \Vert\phi(\mathbf{x})-m\Vert\]

여기서 $m$은 $\mathcal{S}$ 의 중심으로 $m=\frac{1}{n}\sum_{i=1}^n\phi(\mathbf{x_i})$ 로 정의한다. 그러나 커널 트릭을 사용한다면, 특성공간으로의 사상을 계산할 필요 없이 커널을 이용해 바로 거리를 측정할 수 있다.

\[dist(\mathbf{x},\mathcal{S})=\sqrt{k(\mathbf{x,x})-\frac{2}{n}\sum_ik(\mathbf{x,x_i})+\frac{1}{n^2}\sum_i\sum_jk(\mathbf{x_i,x_j})}\]

표현자 정리^{Representer Theorem}

RKHS(Reproducing Kernel Hilbert Space)

표현자 정리를 설명하기에 앞서, 설명에 필요한 RKHS에 대해 살펴보고 가자. 말그대로, RKHS는 힐베르트 공간의 일종인데, 쉽게 말하면 RKHS의 어떤 함수 $f,g$ 가 노음에서 근접하면, 즉 $\Vert f-g\Vert$ 가 작아지면 임의의 $x$에 대해 $\vert f(x)-g(x)\vert$ 도 작아짐을 의미한다.

재생커널힐베르트공간
임의의 집합 $X$에 대해 $H$를 $X$에서의 실함수들의 집합인 힐베르트 공간이라고 정의하자(점별합과 스칼라곱이 정의됨). 이때 임의의 $f\in H$에 대해 선형범함수 $L_x:f\mapsto f(x)$ 를 정의하자. 이때 $L_x:H\to \mathbb{R}$ 이 유계(유계선형범함수)이면 $H$를 RKHS라고 한다. 즉,

\[\vert L_x(f)\vert \leq M_x\cdot\Vert f\Vert_H\quad \forall f\in H\]

이 성립하는 $M_x$가 존재한다.
이때, 리즈표현정리에 의해 다음이 성립한다. RKHS에서 유계선형범함수 $L_x$가 주어지므로, 임의의 $x\in X$ 에 대해 유일한 $K_x\in H$가 대응되어

\[f(x)=L_x(f)=\langle f,K_x\rangle_H\]

가 성립한다. 이때 $K_x$도 실함수 힐베르트공간 $H$의 원소이므로, 다른 $X$의 원소 $y\in X$ 에 대해 $L_y$를 생각하면 $L_y$에 대응되는 실함수를 $K_y\in H$ 라고 할 때

\[K_x(y)=L_y(K_x)=\langle K_x,K_y\rangle_H\]

를 얻을 수 있다. 이를 이용하면, $H$에서 커널을 재생^reproduce해낼 수 있다. 즉 커널 $k:X\times X\to \mathbb{R}$ 을 다음과 같이 정의하면

\[k(x,y) = \langle K_x,K_y\rangle_H\]

이는 커널의 성질을 만족한다. 이렇듯, 커널을 reproduce 할 수 있는 공간이라는 의미에서 재생커널힐베르트공간, RKHS 라고 한다.

Representer Theorem

커널 $k$가 부여된 Input Space $\mathbf{X}$와 $\mathbf{X}$에서의 유한데이터셋 \(S=\lbrace \mathbf{x_1\ldots x_n}\rbrace\) 을 고려하자. 이때 n+1개의 입력값에 대한 함수 $\Psi:\mathbb{R^{n+1}\to R}$ 가 마지막 입력값(argument) 에 대해 단조증가라고 하자. 이때, 커널 $k$에 대응되는 RKHS $(\mathcal{H_k},\Vert\cdot\Vert_\mathcal{H_k})$에서의 최적화 문제

\[\min_{f\in\mathcal{H_k}}\Psi(f(\mathbf{x_1}),\ldots,f(\mathbf{x_n}),\Vert f\Vert_\mathcal{H_k})\]

의 해는 다음과 같이 표현된다.

\[f(\mathbf{x})=\sum_{i=1}^n\alpha_ik(\mathbf{x_i,x}),\quad\forall\mathbf{x\in X}\]

증명. 위의 최적화 문제를 $\xi(f,S)$ 를 최소화하는 문제라고 하자. $\mathcal{H_k}$ 의 부분공간

\[\mathcal{H_k^S} = \lbrace f\in\mathcal{H_k}:f(\mathbf{x})=\sum_{i=1}^n\alpha_ik(\mathbf{x_i,x}), (\alpha_1,\cdots,\alpha_n)\in \mathbb{R^n}\rbrace \subset\mathcal{H_k}\]

을 잡자. 그러면 임의의 함수 $f\in\mathcal{H_k}$ 에 대한 직교화(Orthogonalization)을 생각할 수 있는데, $f=f_S+f_\perp$ 로 하여 $f_S$를 $f$의 $\mathcal{H_k^S}$로의 정사영, $f_\perp$ 를 직교여공간으로의 정사영이라고 하자.
이때, 각 함수 $k(\mathbf{x_i},\cdot)$ 는 $\mathcal{H_k^S}$ 의 원소이고, $f_\perp\perp\mathcal{H_k^S}$ 이므로 $f_\perp(\mathbf{x_i})=\langle f_\perp,k(\mathbf{x_i,\cdot})\rangle = 0$ 이 성립한다. 그러므로 $f(\mathbf{x_i})=f_S(\mathbf{x_i})$ 가 성립한다. 또한, 함수공간에서 $\Vert f\Vert^2 = \Vert f_S\Vert^2+\Vert f_\perp\Vert^2$ 가 성립하므로 $\xi(f,S)\geq\xi(f_S,S)$ 이다 (등호는 $f_\perp=0$ 일 때 성립). 또한 조건에서 $\Psi$가 $\Vert f\Vert$ 에 대해 단조증가하므로 $\xi(f,S)$의 최솟값 $f$는 $\mathcal{H_K^S}$의 원소여야 한다 (등호일때 최소이므로).

예시

표현자 정리에 관한 예시는 커널 PCA에서 확인할 수 있다.

References

• An Introduction to Kernel-Based Leaning Algorithms, K.R. Muller et al.
• A primer on kernel methods, J.Philippe Vert et al.